In a packet communication system, congestion may occur in a relay device (equals to a “packet relay device”) that relays a packet. One example, of a congestion control method is a tail drop method. In the tail drop method, a queue included in the relay device stores packets waiting to be transmitted. When the queue is full, the packets that arrive later are discarded until the queue has space. The tail drop method also includes a transmission device for transmitting a packet that performs control for decreasing a transmission rate (for example, a slow start algorithm) if there is no acknowledgement indicating that the packet is received from a reception device of a destination. Therefore, if the relay device discards the packets, the congestion may be eliminated.
In the tail drop method, however, when the queue is full, the packets that arrive later are unconditionally discarded even if the packet is transmitted from a transmission device whose transmission amount is large or a transmission device whose transmission amount is small. Therefore, a phenomenon (global synchronization) in which a plurality of transmission devices decreases the transmission rate all at once and traffic is temporally extremely decreased may occur. When the global synchronization occurs, a use rate of a network is decreased.
In contrast, there is another congestion control method called a “Random Early Detection (RED)” method. In the RED method, the arriving packets are stochastically discarded before the queue included in the relay device is full. When the packets are stochastically discarded, more packets from the transmission device whose transmission amount is large are easily discarded than the packets from the transmission device whose transmission amount is small. Therefore, the RED method may control the occurrence of the global synchronization.
As for the congestion control of the RED method, there is a proposed technique for determining whether or not if the arriving cell is the final cell and discarding the cells other than the final cell at an arbitrary probability. Moreover, there is a proposed technique for reflecting a data storage state by discard control by acquiring distribution information of a queue length and performing packet discard according to the distribution information.
[Patent Document 1] Japanese Laid-open Patent Publication No. 2001-111556
[Patent Document 2] Japanese Laid-open Patent Publication No. 2004-104417